疯狂的馒头---并查集的妙用

疯狂的馒头

Problem

Description

CQF十分喜欢吃馒头，兴奋之下他一下子买了N 个馒头请所有认识他的人吃。

但是CQF不喜欢白色，喜欢红色、黄色、绿色等鲜艳的颜色。于是他把所有白色的馒头排成一列。然后进行M 次染色操作。每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。一个馒头最终的颜色是最后一次染它的颜色。如果一个馒头没有被染过色，那么它的颜色就是白色。

现在CQF已经定好了染色计划：在第i次染色操作中，把第$(i × p + q)\ mod\ N + 1$个馒头和第$(i × q + p)\ mod\ N+1$个馒头之间的馒头染成颜色i，其中p, q是特定的两个正整数。他想立即知道最后每个馒头的颜色。你能帮他吗？

输入格式
第一行四个正整数N ，M ，p，q。
输出格式
一共输出N 行，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。
输入样例

<br>4 3 2 4
输出样例

<br>2<br>2<br>3<br>0
数据规模
$1 ≤ N ≤ 1000000，1 ≤ M ≤ 10000000$

保证所以输入数据中$1 ≤ M∗p+q，M∗q+p ≤ 2^{31}-1$

Solution

题解

//此题需要调整系统栈大小（编译器命令中） 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#define MA (i * p + q) % N + 1
#define MB (i * q + p) % N + 1
#define MAXN 1000000 + 10
using namespace std;
int N, M, p, q;
int x[MAXN], f[MAXN];
inline void ffa(int &r)
{
    if (x[r] > 0)
    {
        ffa(f[r]);
        r = f[r];
    }
}
void print(int t)
{
    if (t < 0)
    {
        putchar('-');
        t = -t;
    }
    if(t > 9)
        print(t / 10);
    putchar(t % 10 + '0');
}
int main(int argc, char **Argv)
{
    freopen("bread.in", "r", stdin);
    freopen("bread.out", "w", stdout);
    cin >> N >> M >> p >> q;
    memset(x, 0, sizeof x);
    for (int i = 1; i <= N; ++i)
        f[i] = i + 1;
    for (int i = M; i >= 1; --i)
    {
        if (i == M - N) break;
        int j = min(MA, MB);
        int k = max(MA, MB);
        ffa(j);
        while (j <= k)
            x[j] = i, ffa(j);
    }
    
    for (register int i = 1; i <= N; ++i)
    {
    	print(x[i]);
    	puts("");
	}
    return 0;
}
//1000000 10000000 16 188